#include <stdio.h>
#include <stdlib.h>

typedef int ElemType; // 自定义元素类型

typedef struct DuLNode
{
  int data;
  struct DuLNode *prior;
  struct DuLNode *next;
} DuLNode, *DuLinkList;

/**
 * 【双向链表】
 * 1. 创建一个空的双向循环链表
 *
 * 该函数分配一个头结点的内存空间，并将头结点的前驱和后继指针
 * 都指向自己，形成一个空的双向循环链表结构。
 *
 * @return DuLinkList 返回创建成功的双向循环链表头指针，如果内存分配失败则返回NULL
 */
DuLinkList CreateList_DuL()
{
  /* 分配头结点内存空间 */
  DuLinkList L = (DuLinkList)malloc(sizeof(DuLNode));
  if (L == NULL)
  {
    printf("内存分配失败！");
    return NULL;
  }
  /* 初始化空循环链表，头结点的前驱和后继都指向自己 */
  L->prior = L;
  L->next = L;
  return L;
}

/**
 * 获取双链表L中第k个元素节点的指针
 * @param L 双向循环链表头指针
 * @param k 索引
 * @return DuLNode* 找到返回节点指针，否则返回NULL
 */
DuLNode *GetNode_DuL(DuLinkList L, int k)
{
  if (L == NULL || k < 0)
    return NULL; // 链表不存在或k为负数（不合法）

  int j = 0;
  DuLNode *p = L; // 从“头结点”开始（j=0对应头结点）

  // 遍历到第k个节点
  while (p != NULL && j < k)
  {
    p = p->next;
    j++;
    // 避免循环链表中无限循环（若k超出链表长度，p最终会回到L）
    if (p == L)
      break;
  }

  // 若j == k，说明找到第k个节点；否则位置不合法
  return (j == k) ? p : NULL;
}

/**
 * 2. 在双链表L中第i个位置插入元素e
 *
 * @param L 双向循环链表头指针
 * @param i 插入位置
 * @param e 插入元素
 * @return int 插入成功返回1，否则返回0
 */
int ListInsert_DuL(DuLinkList L, int i, ElemType e)
{
  if (L == NULL)
    return 0; // 链表不存在，插入失败

  int j = 0;
  DuLNode *p = GetNode_DuL(L, i - 1);
  if (p == NULL)
    return 0; // 位置i不合法

  DuLNode *s = (DuLNode *)malloc(sizeof(DuLNode)); // 为新节点分配内存
  if (s == NULL)
  {
    printf("Memory allocation failed!\n");
    return 0;
  }
  s->data = e; // 新节点存入值

  // 步骤1：新节点 -> 后继节点（先连后继，避免断链）
  s->next = p->next;  // 新节点的next指向“前驱节点的原后继”
  p->next->prior = s; // 原后继节点的prior指向新节点

  // 步骤2：前驱节点 -> 新节点
  s->prior = p; // 新节点的prior指向“前驱节点”
  p->next = s;  // 前驱节点的next指向新节点

  return 1; // 插入成功
}

/**
 * 3. 删除双链表L中第i个元素，并返回该元素的值
 *
 * @param L 双向循环链表头指针
 * @param i 删除位置
 * @param e 删除元素
 * @return int 删除成功返回1，否则返回0
 */
int ListDelete_DuL(DuLinkList L, int i, ElemType *e)
{
  if (L == NULL || L->next == L)
    return 0; // 链表不存在或为空表

  DuLNode *p = GetNode_DuL(L, i);
  // 额外判断：找到的节点不能是头结点（因为头结点不存储数据）
  if (p == NULL || p == L)
    return 0; // 位置i不合法（p不能是头结点）

  *e = p->data; // 用e带回被删节点的值

  // 调整指针：前驱节点 -> 后继节点（跳过被删节点）
  p->prior->next = p->next;  // 前驱节点的next指向“被删节点的后继”
  p->next->prior = p->prior; // 后继节点的prior指向“被删节点的前驱”

  free(p);  // 释放被删节点的内存
  return 1; // 删除成功
}

/**
 * 4. 正向遍历（从第一个元素到最后一个元素）
 * @param L 双向循环链表头指针
 */
void TraverseList_DuL_Forward(DuLinkList L)
{
  if (L == NULL || L->next == L)
  {
    printf("Empty list!\n");
    return;
  }
  DuLNode *p = L->next; // p指向第一个元素节点
  while (p != L)
  { // 未回到头结点，继续遍历
    printf("%d ", p->data);
    p = p->next; // 后继指针后移
  }
  printf("\n");
}

/**
 * 5. 反向遍历（从最后一个元素到第一个元素）
 * @param L 双向循环链表头指针
 */
void TraverseList_DuL_Backward(DuLinkList L)
{
  if (L == NULL || L->next == L)
  {
    printf("Empty list!\n");
    return;
  }
  DuLNode *p = L->prior; // p指向最后一个元素节点
  while (p != L)
  { // 未回到头结点，继续遍历
    printf("%d ", p->data);
    p = p->prior; // 前驱指针前移
  }
  printf("\n");
}

/**
 * 打印双向循环链表
 * @param L 双向循环链表头指针
 */
void PrintList_DuL(DuLinkList L)
{
  if (L == NULL || L->next == L)
  {
    printf("链表为空\n");
    return;
  }

  DuLinkList p = L->next;
  printf("链表元素: ");
  while (p != L)
  {
    printf("%d ", p->data);
    p = p->next;
  }
  printf("\n");
}

/**
 * 6. 查找双链表L中值为e的元素，并返回该元素所在节点的指针
 * @param L 双向循环链表头指针
 * @param e 查找元素
 * @return DuLNode* 找到返回节点指针，否则返回NULL
 */
DuLNode *LocateElem_DuL(DuLinkList L, ElemType e)
{
  if (L == NULL || L->next == L)
    return NULL; // 空表，直接返回NULL

  DuLNode *p = L->next; // 从第一个元素节点开始遍历
  while (p != L && p->data != e)
  {
    p = p->next; // 未找到目标值，后继指针后移
  }
  return (p != L) ? p : NULL; // 找到返回节点指针，否则返回NULL
}

/**
 * 7. 销毁双链表L
 * @param L 双向循环链表头指针
 */
void DestroyList_DuL(DuLinkList *L)
{
  if (*L == NULL)
    return; // 链表已空，直接返回

  DuLNode *p = (*L)->next; // p从“第一个元素节点”开始
  DuLNode *q;              // 临时指针，保存下一个节点

  while (p != *L)
  {              // 未回到头结点，继续释放
    q = p->next; // 保存下一个节点的地址
    free(p);     // 释放当前节点
    p = q;       // 指针后移，处理下一个节点
  }
  free(*L);  // 释放头结点
  *L = NULL; // 头指针置空，防止野指针
}

int main()
{
  DuLinkList L = CreateList_DuL(); // 创建空双向循环链表
  if (L == NULL)
    return -1;

  // ---------- 测试：插入元素 ----------
  ListInsert_DuL(L, 1, 10);
  ListInsert_DuL(L, 2, 20);
  ListInsert_DuL(L, 3, 30);

  // 打印链表
  PrintList_DuL(L);

  // 在第一个位置插入元素
  printf("在第一个位置插入元素：");
  ListInsert_DuL(L, 1, 5);
  PrintList_DuL(L);

  // 在中间位置插入元素
  printf("在中间位置插入元素：");
  ListInsert_DuL(L, 3, 15);
  PrintList_DuL(L);

  printf("正向遍历链表：");
  TraverseList_DuL_Forward(L);

  printf("反向遍历链表：");
  TraverseList_DuL_Backward(L);

  // ---------- 测试：查找元素 ----------
  ElemType target = 20;
  DuLNode *find = LocateElem_DuL(L, target);
  if (find != NULL)
  {
    printf("找到元素%d，其前驱值为%d，后继值为%d\n",
           find->data, find->prior->data, find->next->data);
  }
  else
  {
    printf("未找到元素%d\n", target);
  }

  // ---------- 测试：删除元素 ----------
  ElemType delVal;
  if (ListDelete_DuL(L, 2, &delVal))
  {
    printf("删除了元素%d，删除后正向遍历：", delVal);
    TraverseList_DuL_Forward(L);
  }
  else
  {
    printf("删除失败\n");
  }

  // ---------- 测试：销毁链表 ----------
  DestroyList_DuL(&L);
  if (L == NULL)
  {
    printf("链表已销毁\n");
  }

  return 0;
}